// https://www.lintcode.com/problem/find-the-celebrity/


// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    /**
     * @param n a party with n people
     * @return the celebrity's label or -1
     */
    int findCelebrity(int n) {
    // 法一：
    // • 对每个做一次名人检验，看是不是所有人都认识他，
    // 但他不认识所有人
    // • 时间复杂度O(n2)
        // for (int i = 0; i < n; i++)
        // {
        //     int j = 0;
        //     for (; j < n; j++)
        //     {
        //         if (j == i)
        //         {
        //             continue;
        //         }
        //         if ((!knows(j, i)) || knows(i, j))
        //         {
        //             break;
        //         }
        //     }
        //     if (j == n)
        //     {
        //         return i;
        //     } 
        // }
        // return -1;
        
    // 法二：
    // • 一次询问knows(a, b): true a认识 b a一定不是名人
    // • false a不认识b b一定不是名人
    // • 所以一次询问就可以排除一个人，n-1询问后剩下一个人，再对这个做
    // 个名人检验就能确定他是否为名人
    // • 所以实现上就是从左到右扫一遍，每次都是保留下的人和新的人做一次
    // 询问，最开始保留的人设为第1个人

    // ◆ 小技巧总结：
    // • 降时间复杂度 - > 找冗余
    // • 思维上双向：true时候，false的时候？

    //   int ans = 0;
    //   for (int i = 1; i < n; i ++)
    //   {
    //       if (knows(ans, i))
    //       {
    //           ans = i;
    //       }
    //   }
    //   for (int i = 0; i < n; i++)
    //   {
    //       if (ans == i)
    //       {
    //           continue;
    //       }
    //       if (knows(ans, i) || (!knows(i, ans)))
    //       {
    //           return -1;
    //       }
    //   }
    //   return ans;
    
        
         //   int ans = 0;
    //   for (int i = 1; i < n; i ++)
    //   {
    //       if (knows(ans, i))
    //       {
    //           ans = i;
    //       }
    //   }
    //   for (int i = 0; i < n; i++)
    //   {
    //       if (ans == i)
    //       {
    //           continue;
    //       }
    //       if (knows(ans, i) || (!knows(i, ans)))
    //       {
    //           return -1;
    //       }
    //   }
    //   return ans;
    
    int left = 0;
    int right = n - 1;
    while (left < right)
    {
        if (knows(left, right))
        {
            left++;
        }
        else
        {
            right--;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (i == left || knows(i, left) && (!knows(left, i)))
        {
            continue;
        }
        else
        {
            return -1;
        }
    }
    return left;
    }
};